package com.leetcode.根据数据结构分类.数组;

import java.util.ArrayList;
import java.util.List;

/**
 * @author: ZhouBert
 * @date: 2021/3/15
 * @description: 54. 螺旋矩阵
 * https://leetcode-cn.com/problems/spiral-matrix/
 */
public class B_54_螺旋矩阵 {

	static B_54_螺旋矩阵 action = new B_54_螺旋矩阵();

	public static void main(String[] args) {
//		test1();
		test2();
	}

	public static void test1() {
		int[][] matrix = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
		List<Integer> res = action.spiralOrder(matrix);
		System.out.println("res = " + res);
	}

	public static void test2() {
		//[1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10]
		int[][] matrix = {{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}, {13, 14, 15, 16}};
		List<Integer> res = action.spiralOrder(matrix);
		System.out.println("res = " + res);
//
	}


	/**
	 * 感觉明确走的方向和边界即可：
	 * 方向：[right, down, left, up]
	 *
	 * @param matrix
	 * @return
	 */
	public List<Integer> spiralOrder(int[][] matrix) {
		int[] direactions = new int[]{0, 1, 2, 3};
		//行
		int m = matrix.length;
		//列
		int n = matrix[0].length;
		int size = m * n;
		List<Integer> res = new ArrayList<>(size);
		int rightLimitIndex = n - 1, downLimitIndex = m - 1, leftLimitIndex = 0, upLimitIndex = 0;
		int dIndex = 0;
		while (res.size() < size) {
			switch (dIndex) {
				//向右，最终更新 upLimitIndex
				case 0:
					for (int i = leftLimitIndex; i <= rightLimitIndex; i++) {
						res.add(matrix[upLimitIndex][i]);
					}
					upLimitIndex++;
					break;
				//向下
				case 1:
					for (int i = upLimitIndex; i <= downLimitIndex; i++) {
						res.add(matrix[i][rightLimitIndex]);
					}
					rightLimitIndex--;
					break;
				//向左
				case 2:
					for (int i = rightLimitIndex; i >= leftLimitIndex; i--) {
						res.add(matrix[downLimitIndex][i]);
					}
					downLimitIndex--;
					break;
				//向上
				case 3:
					for (int i = downLimitIndex; i >= upLimitIndex; i--) {
						res.add(matrix[i][leftLimitIndex]);
					}
					leftLimitIndex++;
					break;
			}
			if (dIndex == 3) {
				dIndex = 0;
			} else {
				dIndex++;
			}

		}
		return res;
	}
}
